1. Technical Field
The present invention relates to a method and algorithm for performing a sequence of integer divides without propagation of truncation error.
2. Related Art
Real-time video systems requiring large network bandwidth generally have their video signals compressed so that the video signals may be efficiently transmitted from source to destination. An example of an emerging video compression standard is the Moving Picture Experts Group (MPEG) standard. Under MPEG, video frames are initially encoded (i.e., compressed) for efficient transmission, placed in a buffer, and subsequently decoded (i.e., uncompressed) for viewing.
During the encoding and decoding of video signals, a Video Buffering Verifier (VBV) buffer is dynamically filled with binary bits of encoded video data at a variable rate (in bits/frame), and the video data is subsequently removed from the buffer at a constant rate (in bits/frame) for decoding purposes. The constant bits/frame removal rate is referred to herein as an average bits/frame (BA), which is computed asBA=BR/FR  (1)wherein BR is a bit rate in bits/second and FR is a frame rate in frames/sec. If integer arithmetic is used by buffer management software to compute BA, then Equation (1) should be recast into an integer format. For example if FR=29.97 frames/sec, thenBA=BR/29.97=BR/(30−0.03)=BR/(30−{fraction (30/1000)})=BR/(30(1−{fraction (1/1000)}))  (2)Expanding (1−{fraction (1/1000)}) in a Taylor series,(1−{fraction (1/1000)})−1=1+{fraction (1/1000)}+terms of second order and higher in {fraction (1/1000)}  (3)Thus to first order, substitution of Equation (3) into Equation (2) yields:BA=(BR+BR/1000)/30  (4)Equation (4) is a representation of Equation (1) to first order of {fraction (1/1000)}. Unfortunately, integer division by 1000 and by 30 in Equation (4) causes truncation error, which results in a smaller computed value of BA than is the “true” value of BA. The “true” value of BA is the constant number of bits/frame physically removed, while the smaller computed value of BA is the bits/frame that the buffer management software tracks as being removed based on Equation (4). For example, if BR=29970 bits/sec, then using Equation (4) with floating point arithmetic yields a “true” value of 1000 bits/frame (actually 999.999 bits/frame) for BA, but using Equation (4) with integer divides by 1000 and 30 yields a smaller computed of 999 bits/frame for BA. Accordingly with integer divides, the buffer management software would account for removal of video data at 999 bits/frame from the VBV buffer, while in actuality 1000 bits/frame is physically removed from the VBV buffer. If B represents the number of bits stored in the VBV buffer at any given time, then B will be computed as a smaller value BC by the buffer management software than the true value BT. As video frames are processed, BT−BC will grow in magnitude and thus pose a risk that eventually BC will be so small in comparison with BT that the buffer management software will erroneously attempt to extract more bits from the VBV buffer than is actually in the VBV buffer. In accordance with the MPEG-2 standards, such an erroneous attempt would cause a VBV buffer violation labeled as “buffer overflow.”
Thus, there is a need to avoid buffer overflow during encoding and decoding of video frames of a video signal.